#if 0
四个基础排序算法:快速排序，归并排序，希尔排序，堆排序
对4个排序算法，分别测试一下效率，并分析一下原因
#endif

//#if 0
#include<iostream>
#include<time.h>
#include<stdlib.h>
using namespace std;

//1.快速排序
int MedianOfThree(int arr[], int left, int right) {
    // 计算中间位置索引，避免溢出
    int mid = left + (right - left) / 2;
    // 确保 arr[left] <= arr[mid]
    if (arr[left] > arr[mid]) {
        int temp = arr[left];
        arr[left] = arr[mid];
        arr[mid] = temp;
    }
    // 确保 arr[left] <= arr[right]
    if (arr[left] > arr[right]) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
    // 确保 arr[mid] <= arr[right]
    if (arr[mid] > arr[right]) {
        int temp = arr[mid];
        arr[mid] = arr[right];
        arr[right] = temp;
    }
    // 将中间值放到 left 位置
    int temp = arr[left];
    arr[left] = arr[mid];
    arr[mid] = temp;
    // 返回基准数
    return arr[left];
}
//快排分割处理函数
int Partition(int arr[], int left, int right) {
    /*int val = arr[left];//先将起始位置的元素当做基准数*/
    // 使用三数取中法选择基准数
    int val = MedianOfThree(arr, left, right);

    //进行分割的条件是left<right
    while (left < right) {
        //进行快排分割处理:
        while (arr[right] >= val && left < right) { // 从右向左找第一个小于val的数，但是要注意left<right，否则会越界
            right--;
        }

        //找到了 一个有效的数字
        if (left < right) {
            arr[left] = arr[right];//将右边的找到的数字放到左边
            left++;//找到后右移
        }

        while (arr[left] <= val && left < right) { // 从左向右找第一个大于val的数，但是要注意left<right，否则会越界
            left++;
        }
        if (left < right) {
            arr[right] = arr[left];//将左边找到的数字放到右边
            right--;//找到后左移
        }
    }
    //lef==right的位置就是放基准数的位置，将基准数放在这个位置(left)
    arr[left] = val;

    return left;//返回基准数的位置
}
//快排的递归接口
void QuickSort(int arr[], int left, int right) {
    //递归结束的条件
    if (left >= right) {
        return;
    }
    /*1.随着快排算法执行，数据越来越趋于有序，在一定范围内可以采用插入排序代替快速排序*/
    //当[left,right]序列的元素个数小到指定数量，采用插入排序，这里指定为50
    if (right - left <= 50) {//预设50个元素以内采用插入排序，根据数据规模设计
        //对指定的left到right区间内进行插入排序
        for (int i = left + 1; i <= right; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
        return;
    }
    //在left 和 right区间的元素做一次快排分割处理
    int pos = Partition(arr, left, right);//pos是返回的基准数放的位置
    /*3.尾递归优化（减少递归栈空间）*/
    /*
    //对基准数的左边和右边的序列再分别进行快排，这里直接递归调用即可
    QuickSort(arr, left, pos - 1);//基准数位置为pos，上下界根据pos划分
    QuickSort(arr, pos + 1, right);
    */
    // 尾递归优化：处理较小子数组，循环处理较大子数组
    if (pos - left < right - pos) {
        QuickSort(arr, left, pos - 1); // 尾递归（较小子数组）
        left = pos + 1; // 循环处理较大子数组
    }
    else {
        QuickSort(arr, pos + 1, right); // 尾递归（较小子数组）
        right = pos - 1; // 循环处理较大子数组
    }
}
//快速排序
void QuickSort(int arr[], int size) {
    //封装一个快排的递归接口
    return QuickSort(arr, 0, size - 1);
}

//2.归并排序
//定义一个合并的函数
void Merge(int arr[], int left, int mid, int right,int*temp) {
    //对[left, mid]和[mid + 1, right] 两个小段区间的有序序列 进行归并为大段有序序列

    //int* temp = new int[right - left + 1];//开辟内存空间,临时数组存放合并元素
    int idx = 0;//临时数组的下标
    int i = left;//指向左区间的起始位置
    int j = mid + 1;//指向右区间的起始位置

    while (i <= mid && j <= right) {
        //循环比较左右两个区间的元素,哪个小就先放入临时数组
        if (arr[i] <= arr[j]) {
            temp[idx] = arr[i];
            i++;
            idx++;
        }
        else {
            temp[idx++] = arr[j++];
        }
    }

    //不确定是左边还是右边先排完，没有剩余的元素，所以要进行判断
    while (i <= mid) { //说明左边的小段还有剩余
        temp[idx++] = arr[i++];//将左边剩余的元素依次放入临时数组
    }
    while (j <= right) { //说明右边的小段还有剩余
        temp[idx++] = arr[j++];//将右边剩余的元素依次放入临时数组
    }

    //再把合并好的较大段的有序结果，拷贝到原始数组arr的[1,right]区间
    for (i = left, j = 0; i <= right; i++, j++) {//复用一下i,j
        //原始数组是从[left,right]区间的，我们合并的数组是从区间[0]开始的，所以i从left开始，j从0开始
        //当i到right时，j中元素也就已经遍历完，全部拷贝完毕
        arr[i] = temp[j];
    }
    //delete[]temp;//释放内存

/*
下面测试看来归并耗时比较长，超出预期了，可能是临时开辟空间然后删除，数据量过大导致的，这里优化，在一开始的时候就开辟一个大段空间
*/

}
//定义一个归并排序递归接口
void MergeSort(int arr[], int left, int right,int *temp) {
    //实现功能：先递，在[left,right]区间的数据进行归并排序，再归进行合并

    //递：
    //递归结束条件：left >= right
    if (left >= right) {
        return;
    }
    //递的逻辑：
    int mid = (left + right) / 2;
    MergeSort(arr, left, mid,temp);//递归排序左边
    MergeSort(arr, mid + 1, right,temp);//递归排序右边

    //归并的逻辑：
    //对[left,mid]和[mid+1,right] 两个小段区间的有序序列 进行归并为大段有序序列
    Merge(arr, left, mid, right,temp);
}
//归并排序
void MergeSort(int arr[], int size) {
    //开辟一大段空间
    int* temp = new int[size];
    MergeSort(arr, 0, size - 1,temp);
    //释放空间
    delete[] temp;
    //修改几个接口，都加上一个*temp的参数
}

//3.堆排序
//堆的下沉调整
void siftDown(int arr[], int i, int size)
{
    int val = arr[i];//先保存要调整的元素，防止待会提上来元素值较大的孩子节点元素覆盖掉
    while (i < size / 2) {
        //先让child记录值比较大的那个孩子节点的下标
        int child = 2 * i + 1;//左孩子
        //如果右孩子大就更新child记录右孩子节点的下标，不过要先判断一下有没有右孩子节点
        if (child + 1 < size && arr[child + 1] > arr[child]) {//有右孩子，且大于左孩子
            child = child + 1;
        }

        //如果孩子节点的值大于要调整的元素，则交换位置，否则跳出循环
        if (val < arr[child]) {
            arr[i] = arr[child];//将孩子节点往上提
            i = child;//更新i，继续指向它的孩子，继续调整直到下沉到叶子节点
        }
        else {//满足了堆的规则，跳出循环
            break;
        }
    }
    arr[i] = val; // 将暂存的val放回正确位置
}

//堆排序
void HeapSort(int arr[], int size) {
    int n = size - 1;//末尾元素下标n
    //从第一个非叶子节点（n-1）/2开始
    for (int i = (n - 1) / 2; i >= 0; i--) {
        siftDown(arr, i, size);//从第i个位置开始调整堆结构
    }

    //现在相当于已经将原始的元素调整为大根堆了，只要将堆顶元素和末尾元素交换位置，从堆顶进行下沉调整，直到调整完所有元素
    for (int i = n;i > 0;i--) {//i=0只剩堆顶一个元素了，就不用下沉调整了，没必要，这里i>0就行
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        siftDown(arr, 0, i);//每次进行调整的时候，堆顶元素已经调整到正确的位置了，参与调整的元素个数-1
        //第三个参数表示参与调整的元素个数，每次调整都会--，所以直接用i即可
    }
}



//4.希尔排序
void shellSort(int arr[], int size) {
    //希尔排序是基于插入排序基础上在每次进行插入排序的时候，多了对序列进行分组的操作
    for (int gap = size / 2; gap > 0; gap /= 2) {
        //下面是插入排序的代码：将其中的部分条件改为以gap为步长约束的条件即可
        //----------------------
        for (int i = gap; i < size; i++) {     //O(n)
            //改：for (int i = 1; i < size; i++) {
            int val = arr[i];
            int j = i - gap;
            //改：int j = i - 1;
            for (;j >= 0;j -= gap) {           //O（n） 
                //改：for (; j >= 0; j--) {

                if (arr[j] > val) {
                    arr[j + gap] = arr[j];
                    //改：arr[j + 1] = arr[j];
                }
                else {
                    break;
                }
            }
            arr[j + gap] = val;
            //改:arr[j + 1] = val;
        }
        //------------------------
    }
}

int main() {
    cout<< "RAND_MAX="<< RAND_MAX << endl;

    //用系统时间种随机数种子
    srand(time(NULL));

    //数据量比较大，最好不要把数据定义在栈上，而是定义在堆上。
    const int COUNT = 100000000;
    int* arr = new int[COUNT];
    int* brr = new int[COUNT];
    int* crr = new int[COUNT];
    int* drr = new int[COUNT];
    cout << "COUNT=" << COUNT << endl;

    for (int i = 0; i < COUNT; i++) {
        int val = rand() % COUNT;
        //rand()%的范围在0-32767,这个范围的随机数在100000和1000000、100000000的数据量下，重复太多了
        //可以分为0-32767   32767 - 32768+32767 的区间，这样重复的概率就低了
        arr[i] = val;
        brr[i] = val;
        crr[i] = val;
        drr[i] = val;
    }

    clock_t start, end;
    /*clock_t start, end; 是在 C 或 C++ 语言中用于计时的变量定义语句，clock_t是一种数据类型，
    通常被定义为长整型（long） ，用于保存时间相关的值。其作用主要是配合clock()函数来计算某段代码的执行时间
    需要注意，clock()函数返回的是 CPU 时间，即程序实际占用 CPU 运行的时间，不包括程序在等待 I/O 操作等非 CPU 运行时间；
    并且该函数的计时精度通常只能达到毫秒级别*/

    start = clock();//先记录当前的时间戳
    QuickSort(arr, COUNT);
    end = clock();//获取冒泡排序后的时间戳
    cout << "快速排序耗时：" << (end - start) * 1.0 / CLOCKS_PER_SEC << "s" << endl;//将时间戳转换成秒级别的单位
    /*CLOCKS_PER_SEC是<time.h>头文件中定义的宏，表示每秒的时钟计时单元数。
    (end - start)*1.0/CLOCKS_PER_SEC 这部分整体是将计时单元数差值转换为以秒为单位的时间*/

    start = clock();
    MergeSort(brr, COUNT);
    end = clock();
    cout << "归并排序耗时：" << (end - start) * 1.0 / CLOCKS_PER_SEC << "s" << endl;

    start = clock();
    HeapSort(crr, COUNT);
    end = clock();
    cout << "堆排序耗时：" << (end - start) * 1.0 / CLOCKS_PER_SEC << "s" << endl;

    start = clock();
    shellSort(drr, COUNT);
    end = clock();
    cout << "希尔排序耗时：" << (end - start) * 1.0 / CLOCKS_PER_SEC << "s" << endl;

    // 释放动态分配的内存
    delete[] arr;
    delete[] brr;
    delete[] crr;
    delete[] drr;

    return 0;
}
/*
RAND_MAX=32767
COUNT=10000
快速排序耗时：0s
归并排序耗时：0.014s
堆排序耗时：0.003s
希尔排序耗时：0.006s

RAND_MAX=32767
COUNT=100000000
快速排序耗时：1.887s
归并排序耗时：105.852s
堆排序耗时：59.959s
希尔排序耗时：86.728s

//这里的归并排序时间有点问题，优化后结果:

RAND_MAX=32767
COUNT=10000
快速排序耗时：0s
归并排序耗时：0.005s
堆排序耗时：0.005s
希尔排序耗时：0.005s

RAND_MAX=32767
COUNT=100000000
快速排序耗时：1.893s
归并排序耗时：32.569s
堆排序耗时：55.468s
希尔排序耗时：64.602s

RAND_MAX=32767 
COUNT=100000000
快速排序耗时：0.859s
归并排序耗时：25.432s
堆排序耗时：50.697s
希尔排序耗时：69.418s

//总结：
1、 不管是快排，或者归并排序，遍历元素的时候都是按照顺序遍历的，对 CPU 缓存是友好的（CPU 缓存命中率高），
    但是堆排序，访问元素的时候，是按照父子节点的关系访问的，并不是按照顺序访问的，所以排序过程中，
    不管是进行元素上浮调整，还是下沉调整，对 CPU 缓存不友好。
2、 堆排序过程中，进行元素下沉调整所做的无效比较过多
    因为它本身就小，所以最终下沉到的地方，和末尾距离相差不远，中间做了很多无效比较多

*/
//#endif